"""
221. 最大正方形 - 测试数据生成器

用于生成各种类型的测试数据，验证算法的正确性和性能
"""

import random
from typing import List, Tuple

class TestDataGenerator:
    """测试数据生成器"""
    
    def __init__(self, seed: int = 42):
        """初始化随机种子以确保可重现性"""
        random.seed(seed)
    
    def generate_basic_cases(self) -> List[Tuple[str, List[List[str]]]]:
        """生成基本测试用例"""
        return [
            ("示例1", [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]),
            ("示例2", [["0","1"],["1","0"]]),
            ("示例3", [["0"]]),
            ("全1矩阵", [["1","1"],["1","1"]]),
            ("全0矩阵", [["0","0"],["0","0"]]),
        ]
    
    def generate_boundary_cases(self) -> List[Tuple[str, List[List[str]]]]:
        """生成边界测试用例"""
        return [
            ("单行单列", [["1"]]),
            ("单行多列", [["1","0","1","1"]]),
            ("多行单列", [["1"],["0"],["1"],["1"]]),
            ("2x2全1", [["1","1"],["1","1"]]),
            ("3x3全1", [["1","1","1"],["1","1","1"],["1","1","1"]]),
            ("大正方形", [["1","1","1","1"],["1","1","1","1"],["1","1","1","1"],["1","1","1","1"]]),
        ]
    
    def generate_matrix(self, rows: int, cols: int, one_probability: float = 0.5) -> List[List[str]]:
        """生成指定大小的随机矩阵"""
        matrix = []
        for i in range(rows):
            row = []
            for j in range(cols):
                if random.random() < one_probability:
                    row.append("1")
                else:
                    row.append("0")
            matrix.append(row)
        return matrix
    
    def generate_matrix_with_square(self, rows: int, cols: int, square_size: int) -> List[List[str]]:
        """生成包含指定大小正方形的矩阵"""
        if square_size > min(rows, cols):
            raise ValueError(f"正方形大小 {square_size} 超过矩阵维度 {rows}x{cols}")
        
        # 初始化全0矩阵
        matrix = [["0" for _ in range(cols)] for _ in range(rows)]
        
        # 随机放置正方形
        start_row = random.randint(0, rows - square_size)
        start_col = random.randint(0, cols - square_size)
        
        for i in range(start_row, start_row + square_size):
            for j in range(start_col, start_col + square_size):
                matrix[i][j] = "1"
        
        # 随机添加其他1
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "0" and random.random() < 0.3:
                    matrix[i][j] = "1"
        
        return matrix
    
    def generate_performance_cases(self) -> List[Tuple[str, List[List[str]]]]:
        """生成性能测试用例"""
        cases = []
        
        # 不同规模的随机矩阵
        for size in [5, 10, 20, 50]:
            matrix = self.generate_matrix(size, size, 0.6)
            cases.append((f"随机矩阵_{size}x{size}", matrix))
        
        # 不同密度的矩阵
        for density in [0.2, 0.5, 0.8]:
            matrix = self.generate_matrix(10, 10, density)
            cases.append((f"密度{density}_10x10", matrix))
        
        # 包含特定大小正方形的矩阵
        for square_size in [2, 3, 4, 5]:
            matrix = self.generate_matrix_with_square(15, 15, square_size)
            cases.append((f"包含{square_size}x{square_size}正方形", matrix))
        
        return cases
    
    def generate_special_cases(self) -> List[Tuple[str, List[List[str]]]]:
        """生成特殊结构的测试用例"""
        return [
            ("对角线模式", [["1","0","0"],["0","1","0"],["0","0","1"]]),
            ("十字形", [["0","1","0"],["1","1","1"],["0","1","0"]]),
            ("L形", [["1","0","0"],["1","0","0"],["1","1","1"]]),
            ("空心正方形", [["1","1","1","1"],["1","0","0","1"],["1","0","0","1"],["1","1","1","1"]]),
            ("条纹模式", [["1","0","1","0"],["0","1","0","1"],["1","0","1","0"],["0","1","0","1"]]),
        ]
    
    def generate_all_test_cases(self) -> List[Tuple[str, List[List[str]]]]:
        """生成所有测试用例"""
        all_cases = []
        
        all_cases.extend(self.generate_basic_cases())
        all_cases.extend(self.generate_boundary_cases())
        all_cases.extend(self.generate_special_cases())
        all_cases.extend(self.generate_performance_cases())
        
        return all_cases
    
    def save_test_cases_to_file(self, filename: str = "test_cases.txt"):
        """将测试用例保存到文件"""
        cases = self.generate_all_test_cases()
        
        with open(filename, 'w', encoding='utf-8') as f:
            f.write("# 221. 最大正方形 - 测试用例\n\n")
            
            for i, (name, matrix) in enumerate(cases, 1):
                f.write(f"## 测试用例 {i}: {name}\n")
                f.write(f"矩阵维度: {len(matrix)}x{len(matrix[0]) if matrix else 0}\n")
                f.write("输入矩阵:\n")
                for row in matrix:
                    f.write(f"{row}\n")
                f.write("\n")
        
        print(f"测试用例已保存到 {filename}")
        print(f"共生成 {len(cases)} 个测试用例")

def analyze_matrix_properties(matrix: List[List[str]]) -> dict:
    """分析矩阵的性质"""
    if not matrix or not matrix[0]:
        return {"rows": 0, "cols": 0, "ones_count": 0}
    
    rows, cols = len(matrix), len(matrix[0])
    ones_count = sum(row.count("1") for row in matrix)
    
    return {
        "rows": rows,
        "cols": cols,
        "total_cells": rows * cols,
        "ones_count": ones_count,
        "ones_density": ones_count / (rows * cols),
        "zeros_count": rows * cols - ones_count,
    }

def print_matrix_analysis(name: str, matrix: List[List[str]]):
    """打印矩阵分析结果"""
    props = analyze_matrix_properties(matrix)
    print(f"\n=== {name} ===")
    print(f"矩阵维度: {props['rows']}x{props['cols']}")
    if props['rows'] > 0:
        print(f"总单元格数: {props['total_cells']}")
        print(f"1的个数: {props['ones_count']}")
        print(f"0的个数: {props['zeros_count']}")
        print(f"1的密度: {props['ones_density']:.2f}")
        
        # 打印矩阵（如果不太大）
        if props['rows'] <= 5 and props['cols'] <= 10:
            print("矩阵内容:")
            for row in matrix:
                print(" ".join(row))

def main():
    """主函数 - 生成并分析测试数据"""
    print("221. 最大正方形 - 测试数据生成器")
    print("=" * 50)
    
    generator = TestDataGenerator()
    
    # 生成基本测试用例
    print("\n基本测试用例:")
    basic_cases = generator.generate_basic_cases()
    for name, matrix in basic_cases:
        print_matrix_analysis(name, matrix)
    
    # 生成边界测试用例
    print("\n边界测试用例:")
    boundary_cases = generator.generate_boundary_cases()
    for name, matrix in boundary_cases:
        print_matrix_analysis(name, matrix)
    
    # 生成特殊测试用例
    print("\n特殊测试用例:")
    special_cases = generator.generate_special_cases()
    for name, matrix in special_cases:
        print_matrix_analysis(name, matrix)
    
    # 保存所有测试用例到文件
    generator.save_test_cases_to_file()
    
    # 生成一些随机测试用例进行快速验证
    print("\n随机测试用例示例:")
    for i in range(3):
        size = random.randint(3, 6)
        matrix = generator.generate_matrix(size, size, 0.5)
        print_matrix_analysis(f"随机用例{i+1}", matrix)

if __name__ == "__main__":
    main()

